package backtracking.nowcoder.medium;

import java.util.*;

/**
 * @author bruin_du
 * @description 迷宫问题
 * https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?
 * tpId=37&&tqId=21266&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
 * @date 2022/5/21 9:49
 **/
public class MazeProblem {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNextInt()){
            int N = in.nextInt();
            int M = in.nextInt();
            int[][] maze = new int[N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    maze[i][j] = in.nextInt();
                }
            }
            Deque<Coord> stack = new ArrayDeque<>();
            findPath(maze,stack,N,M,0,0);
            while(!stack.isEmpty())
                System.out.println(stack.pollLast());
        }
    }

    private static boolean findPath(int[][] maze, Deque<Coord> stack, int N, int M, int row, int col) {
        if(row == -1 || col == -1 || row == N || col == M || maze[row][col] == 1)
            return false;
        if(row == N - 1 && col == M - 1) {
            stack.offerLast(new Coord(row,col));
            return true;
        }
        //把走过的路置为1,防止往回走
        maze[row][col] = 1;
        if(findPath(maze, stack, N, M, row + 1, col) ||
           findPath(maze, stack, N, M, row, col + 1) ||
           findPath(maze, stack, N, M, row - 1, col) ||
           findPath(maze, stack, N, M, row, col - 1)){
            stack.offerLast(new Coord(row, col));
            return true;
        }else
            return false;
    }
}
class Coord{
    int row;
    int col;

    public Coord(int row, int col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public String toString() {
        return "(" + row + "," + col + ")";
    }
}